/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution62 {

    public static void main(String args[]) {
        Solution62 s = new Solution62();
        System.out.println(s.uniquePaths(23, 12));
    }

    public int uniquePaths(int m, int n) {
        int[][] mp = new int[m + 1][n + 1];
        return dfs(1, 1, m, n, mp);
    }

    public int dfs(int x, int y, int m, int n, int[][] mp) {
        if (x == m && y == n) {
            return 1;
        }
        if(mp[x][y] != 0){
            return mp[x][y];
        }
        int right = 0;
        if (y + 1 <= n) {
            right = dfs(x, y + 1, m, n, mp);
        }
        int bottom = 0;
        if (x + 1 <= m) {
            bottom = dfs(x + 1, y, m, n, mp);
        }
        mp[x][y] = right + bottom;
        return mp[x][y];
    }
}
